from LeetCoder import *



class Solution:

    def specialPerm(self, nums: List[int]) -> int:
        n = len(nums)
        mod = 1000000007

        @cache
        def f(index, used:int):
            if used.bit_count() == n:
                return 1
            ans = 0
            num = nums[index]
            for i in range(n):
                if (used >> i) & 1 == 0:
                    if nums[i] % num == 0 or num % nums[i] == 0:
                        ans += f(i, used | (1 << i))
                        ans %= mod
            return ans

        ans = 0
        for i in range(n):
            ans += f(i, 1 << i)
            ans %= mod
        return ans % mod

s = Solution()
print(s.specialPerm([2, 3, 6]))
print(s.specialPerm([1, 4, 3]))
